Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Combination Sum

Problem Statement

Given an array of distinct positive integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1:

Input: candidates = [2, 3, 6, 7], target = 7  
Output: [[2, 2, 3], [7]]  
Explanation: The elements in these two combinations sum up to 7.

Example 2:

Input: candidates = [2, 4, 6, 8], target = 10  
Output: [[2,2,2,2,2], [2,2,2,4], [2,2,6], [2,4,4], [2,8], [4,6]]    
Explanation: The elements in these six combinations sum up to 10.

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40

Solution

This problem is quite similar to the example discussed in the previous lesson (placing apple, orange, and mango trees).

We can follow the brute-force approach to incrementally build the solution.

If, at any time, we find out that the current solution can’t lead to a valid combination, we will abandon it and backtrack to try the remaining solutions.

Let’s try this approach on the following input: Candidates: [3, 4, 5], Target: 9

Image

Here are the number of steps in our algorithm:

  1. We will start with an empty set. This also means that the sum of the elements in the set is zero.
  2. We can try adding all three numbers separately in the set. This will give us three sets: [3], [4], [5].
  3. Let’s take set [3], since the sum of its elements is less than the Target (=9), we will try adding more numbers to it.
  4. We can add all three numbers again to generate new sets. We can add ‘3’ again, as each number can be added multiple times.
  5. After adding all numbers separately to the set [3], we will get the following sets: [3, 3], [3, 4], [3, 5]. We can see, each set has a sum less than the target.
  6. We can now, repeat the same process as described in step-4.
    • For [3, 3]: Adding ‘3’ will give us a valid solution [3, 3, 3] having a sum equal to the target. Adding ‘4’ and ‘5’ will give us a sum which is greater than the target. Therefore, we can stop the search here for this set, as adding any additional number will not produce a correct solution.
    • For [3, 4]: We will add ‘4’ or ‘5’ to it, which will give us a sum greater than the target. We will stop our search here for this set.
    • For [3, 5]: We can only add ‘5’ to it, which does not produce a valid solution.
  7. Similar approach can be applied to other sets.
  8. In the end, we can see that the valid solutions are: [3, 3, 3] and [4, 5].

Code

The basic idea is to start with an empty combination and iterate through the candidates array, adding each candidate to the current combination and recursively calling the function with the updated combination and the remaining target. If the target becomes 0, we add the current combination to the result list. If the target becomes negative, we backtrack and remove the last added candidate from the combination.

The function combinationSum takes in two parameters, an array of distinct integers candidates and a target integer target, and returns a list of all unique combinations of candidates where the chosen numbers sum to target. The function starts by defining the function backtrack(candidates, start, target, comb, res). This function takes five parameters, candidates, start, target, comb, and res:

  • candidates is the array containing candidate elements.
  • start is the starting index of the candidates array.
  • target is the remaining target.
  • comb is the current combination.
  • res is the final result list.

The backtrack function uses recursion to find the combinations. The base case for the recursion is if the target is 0. When the target is 0, that means we have found a valid combination and we append a copy of the current combination to the result list. It then iterates through the candidates array starting from the given index. If the current candidate is greater than the remaining target, it skips the current candidate and move on to the next. If the current candidate is less than the remaining target, it adds the current candidate to the current combination, recursively calls the function with the updated combination and remaining target, and then backtracks by removing the last added candidate from the combination.

Java
Saved to Cloud

. . . .

Time Complexity

This algorithm has a time complexity of , where is the total number of elements in the candidates array, is the target value, and is the smallest value among the candidates. This is because the execution of the backtracking is similar to a DFS traversal of an n-ary tree. So, the time complexity would be the same as the number of nodes in the n-ary tree. This can be seen in the above diagram.

Each node can call the backtrack function a maximum of times, i.e., the total number of candidates. The maximal depth of the n-ary tree would be , where we keep on adding the smallest element to the combination. As we know, the maximal number of nodes in N-ary tree of height would be , hence the time complexity is .

Space Complexity

Ignoring the space needed for the output array, the space complexity will be because at any time, we can pile up to recursive calls of the backtrack function; this will happen when we keep on adding the smallest element to the combination. As a result, the space overhead of the recursion is .

Combination Sum (medium)
Implement Trie (Prefix Tree) (medium)
Mark as Completed

On this page

Problem Statement

Solution

Code

Time Complexity

Space Complexity